package com.LeeCode;

/**
 * 搜索旋转排序数组 II
 */

public class Code081 {
    public static void main(String[] args) {
        int[] nums = {0, 1, 2, 0, 0};
        int target = 1;
        System.out.println(new Code081().search1(nums, target));
    }

    public boolean search(int[] nums, int target) {
        int left = -1, right = nums.length;
        int start = 0, end = nums.length - 1;
        while (left + 1 < right) {
            int mid = (left + right) / 2;
            if (nums[mid] == target) {
                return true;
            }

            if (nums[mid] > nums[end]) {
                if (target >= nums[start] && target <= nums[mid]) {
                    right = mid;
                    end = right;
                } else {
                    left = mid;
                }
            } else if (nums[mid] < nums[end]) {
                if (target > nums[mid] && target <= nums[end]) {
                    left = mid;
                } else {
                    right = mid;
                    end = right;
                }
            } else {
                right--;
                end = right - 1;
            }
        }
        return false;
    }

    public boolean search1(int[] nums, int target) {
        int left = -1, right = nums.length - 1;
        while (left + 1 < right) {
            int mid = (left + right) >> 1;
            if (nums[mid] == nums[right]) {
                right--;
            } else if (check(nums, target, right, mid))
                right = mid;
            else
                left = mid;
        }
        return nums[right] == target;
    }

    // 判断target是否在right的右边
    private boolean check(int[] nums, int target, int right, int index) {
        int x = nums[index];
        if (x > nums[right]) {
            return target > nums[right] && target <= x;
        }

        return target > nums[right] || target <= x;
    }
}
